package promote.brozen.algorithm.tree.binary.bst;

import promote.brozen.algorithm.tree.Tree;
import promote.brozen.algorithm.tree.binary.RecursionBinaryTreeWalker;

import java.util.function.Consumer;

/**
 * Binary Search Tree
 * 二叉搜索树性质：
 *
    1. 若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值；
    2. 若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值；
    3. 它的左、右子树也分别为二叉排序树；
 *
 *
 * @author Brozen
 * @date 2019/12/20 11:12 AM
 */
public class BSTTree<K extends Comparable<K>> implements Tree<K> {

    private BSTTreeNode<K> root;

    /**
     * 插入
     */
    @Override
    public void add(K key) {
        this.root = doAdd(this.root, key);
    }

    private BSTTreeNode<K> doAdd(BSTTreeNode<K> node, K key) {
        if (node == null) {
            return new BSTTreeNode<>(key);
        }

        int compareResult = node.getKey().compareTo(key);
        if (compareResult > 0) {
            BSTTreeNode<K> leftChild = node.getLeftChild();
            node.setLeftChild(doAdd(leftChild, key));
        } else if (compareResult < 0) {
            BSTTreeNode<K> rightChild = node.getRightChild();
            node.setRightChild(doAdd(rightChild, key));
        } else {
            // 相等，则更新
            node.setKey(key);
        }

        return node;
    }


    /**
     * 删除
     * 高度为h的二叉搜索树，删除操作时间复杂度为O(h)
     */
    @Override
    public void remove(K key) {
        this.root = doRemove(this.root, key);
    }

    private BSTTreeNode<K> doRemove(BSTTreeNode<K> node, K key) {
        if (node == null) {
            return null;
        }

        BSTTreeNode<K> leftChild = node.getLeftChild();
        BSTTreeNode<K> rightChild = node.getRightChild();

        int compareResult = node.getKey().compareTo(key);
        if (compareResult > 0) {
            node.setLeftChild(doRemove(leftChild, key));
        } else if (compareResult < 0) {
            node.setRightChild(doRemove(rightChild, key));
        } else {
            if (leftChild == null) {
                // 1. 左子节点为空，用右子节点取代被删除的节点
                node = rightChild;
            } else if (rightChild == null) {
                // 2. 右子节点为空，用左子节点取代被删除的节点
                node = leftChild;
            } else {
                // 有两个子节点，则用后继节点(右子树的最小节点 或 左子树最大节点)代替被删除节点
                // 3.1. 先找到后继节点，这里使用右子树最小节点作为后继节点
                BSTTreeNode<K> successor = min(rightChild);

                // 3.2. 如果后继节点不是被删除节点的右子节点，而是其他子孙节点，需要用后继节点的右子节点代替后继节点
                //      因为后继节点是右子树最小节点，根据二叉搜索树性质，他不可能有左子节点，否则就不是最小节点
                if (successor != rightChild) {
                    successor.getParent().setLeftChild(successor.getRightChild());
                    // 后继节点不是被删除节点的右子节点时，必须设置后继节点右子节点为被删除节点的右子节点，否则指针不对；
                    // 后继节点是被删除节点的右子节点时，不能设置后继节点右子节点为被删除节点的右子节点，否则会出现循环引用：后继节点的右子节点是自己；
                    successor.setRightChild(node.getRightChild());
                }

                // 3.3. 用后继节点代替要被删除的节点，并设置子节点指针
                successor.setLeftChild(node.getLeftChild());
                node = successor;
            }
        }

        return node;
    }

    /**
     * 搜索
     */
    @Override
    public K search(K key) {
        BSTTreeNode<K> node = searchNode(this.root, key);
        return node == null ? null : node.getKey();
    }

    private BSTTreeNode<K> searchNode(BSTTreeNode<K> node, K key) {
        int compareResult;
        if (node == null) {
            return null;
        } else if ((compareResult = node.getKey().compareTo(key)) > 0) {
            return searchNode(node.getLeftChild(), key);
        } else if (compareResult < 0) {
            return searchNode(node.getRightChild(), key);
        } else {
            return node;
        }
    }

    /**
     * 得到子树的最大节点
     */
    private BSTTreeNode<K> max(BSTTreeNode<K> node) {
        while (node.getRightChild() != null) {
            node = node.getRightChild();
        }

        return node;
    }

    /**
     * 得到子树的最小节点
     */
    private BSTTreeNode<K> min(BSTTreeNode<K> node) {
        while (node.getLeftChild() != null) {
            node = node.getLeftChild();
        }

        return node;
    }

    /**
     * 中序遍历
     * 二叉搜索树的中序遍历将得到有序的K
     */
    public void inOrderWalk(Consumer<K> consumer) {
        RecursionBinaryTreeWalker.inOrderTraversal(this.root, consumer);
    }

}
